package leetcode;

/**
 * @author caifangyi
 * @date 2022/8/25
 */

import java.util.*;
import java.util.stream.Collectors;

/**
 * 找到 K 个最接近的元素
 * 给定一个 排序好 的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 *
 * 整数 a 比整数 b 更接近 x 需要满足：
 *
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 * 
 *
 * 示例 1：
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 * 示例 2：
 *
 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
 * 输出：[1,2,3,4]
 * 
 *
 * 提示：
 *
 * 1 <= k <= arr.length
 * 1 <= arr.length<= 104
 * arr按 升序 排列
 * -104<= arr[i], x <= 104
 * 通过次数49,781提交次数106,151
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-k-closest-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


class Day0658 {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        int[] ints = {1,2,3,4,5};
//        List<Integer> closestElements = solution.findClosestElements(ints, 4, 3);
//        String collect = closestElements.stream().map(String::valueOf).collect(Collectors.joining(","));
//        System.out.println(collect);
        int[] ints2 = {1,1,1,10,10,10};
        List<Integer> closestElements2 = solution.findClosestElements(ints2, 1, 9);
        String collect2 = closestElements2.stream().map(String::valueOf).collect(Collectors.joining(","));
        System.out.println(collect2);
    }

    static class Solution {
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            if(arr[0] > x){
                return Arrays.stream(arr).limit(k).mapToObj(Integer::valueOf).toList();
            }
            if(arr[arr.length-1] < x){
                List<Integer> list = new ArrayList<>();
                for (int i = k; i > 0; i--) {
                    list.add(arr[arr.length-i]);
                }
                return list;
            }
            Deque<Integer> left = new ArrayDeque<>();
            Deque<Integer> right = new ArrayDeque<>();

            for (int i = 0; i < arr.length-1; i++) {

                if(arr[i] == x ||(arr[i] < x && arr[i+1] > x)){
                    int l = i, r = i+1;
                    while(k > 0 && l>=0 && r<=arr.length-1){
                        if(x - arr[l] <= arr[r] - x){
                            left.push(arr[l--]);
                        }else{
                            right.push(arr[r++]);
                        }
                        k--;
                    }
                    while (k > 0){
                        if(l<0){
                            right.push(arr[r++]);
                        }else{
                            left.push(arr[l--]);
                        }
                        k--;
                    }
                    List<Integer> list = new ArrayList<>();
                    while (!left.isEmpty()){
                        list.add(left.pollFirst());
                    }
                    while (!right.isEmpty()){
                        list.add(right.pollLast());
                    }
                    return list;
                }

            }

            return Collections.EMPTY_LIST;
        }
    }
}
